import java.util.Arrays;

public class BigHeap{
    
    int[] elem;
    int size;
    
    public BigHeap(int capacity){
        elem = new int[capacity];
    }
    
    public void init(int[] arr){
        for(int i = 0; i<arr.length; i++){
            elem[i] = arr[i];
            size++;
        }
    }
    
    public boolean isFull(){
        return size > elem.length;
    }
    
    public void resize(){
        elem = Arrays.copyOf(elem,size*2);
    }
    
    
    public void createHeap(){
        for(int child = size/2-1; child >=0 ; child--){
            shiftDown(child);
        }
    }
    
    public void shiftDown(int child){
        int parent = 2*child+1;
        while(child < size){
            if(child +1 <size && elem[child] < elem[child+1]){
                child+=1;
            }
            if(elem[parent] < elem[child]){
                swap(elem,parent,child);
                parent = child;
                child = 2*parent+1;
            }else{
                break;
            }
        }
    }
    
    public int poll(){
        if(isFull()){
            resize();
        }
        int ret = elem[0];
        swap(elem,0,size);
        size--;
        shiftDown(0);
        return ret;
    }
    
    public void shiftUp(int child){
        int parent = (child-1)/2;
        while(child != 0){
            if(elem[child] > elem[parent]){
                swap(elem,child,parent);
                child = parent;
                parent = (child-1)/2;
            }
        }
    }

    public void offer(int val){
        elem[size++] = val;
        shiftUp(size-1);
    }

    public void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    
}

